package com.leetcode.algs4.graph;

/**
 * @author Dennis Li
 * @date 2020/6/16 16:41
 */
public class KosarajuSCC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public KosarajuSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];

        // 核心部分 -- 其实完成了两次DFS，在创建order的时候还进行了依次dfs
        DepthFirstOrder order = new DepthFirstOrder(G.reverse());

        for (int s : order.reversePost()) {
            if (!marked[s]) {
                dfs(G, s);
                count++;
            }
        }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]) dfs(G, w);
        }
    }

    public boolean stronglyConnected(int v, int w){
        // 如果所属的连通分量id相同，则证明v和w相互连通
        return id[v] == id[w];
    }

}
